Skip to main content

이분 탐색

이분 탐색은 원하는 데이터의 범위를 절반씩 없애면서 원하는 값을 찾는 알고리즘이다.

분할 정복 기법을 응용한 것으로 배열이 정렬되어 있을때만 사용 가능하다.

왼쪽 값, 오른쪽 값을 설정하고 중간 값이 찾는 값보다 적을 때, 오른쪽 값을 (중간 값 - 1) 로 이동시키고 중간 값이 찾는 값보다 많은 때는 왼쪽 값을 (중간 값 + 1)로 이동시킨다.

이분 탐색 구현​

이분 탐색 애니메이션 에 들어가서 애니메이션을 보시면 이해하기 편합니다

Java 코드입니다.

static int binarySearch(int[] arr, int num) {
  Arrays.sort(arr);

  int left = 0, right = arr.length-1;

  while(left <= right) {
    // 중간 위치 구함
    int mid = (left + right)/2;

    // 위치 찾을 경우
    if(arr[mid] == num) return mid;

    // 중간 값이 찾고자하는 값보다 작을 경우 -> 중간 값 보다 오른쪽에 위치해있다
    if(arr[mid] < num) {
        left = mid + 1;
    }else { // 중간 값이 찾고자하는 값보다 큰 경우 -> 중간 값 보다 왼쪽에 위치해있다
        right = mid - 1;
    }
  }

  // 찾는 값이 없을 경우 -1을 반환(-1이라는 index는 없기 때문)
  return -1;
}

Python 코드입니다.

def binary_search(sorted_collection, item):

    left = 0
    right = len(sorted_collection) - 1

    while left <= right:
        midpoint = (left + right) // 2
        current_item = sorted_collection[midpoint]
        if current_item == item:
            return midpoint
        else:
            if item < current_item:
                right = midpoint - 1
            else:
                left = midpoint + 1
    return None

한번 반복할 때 마다 남은 데이터의 개수의 절반이 사라지므로 시간복잡도는 O(log⁡n)O(\log{n})가 된다.

이분 탐색의 장단점​

장점​

  1. 선형 탐색에 비해 빠른 시간에 정렬할 수 있다.( 시간복잡도 O(log⁡n)O(\log{n}) )

단점​

  1. 정렬이 되어 있는 데이터에만 사용 가능

나올 수 있는 면접 질문​

  • 이분 탐색이란?
  • 이분 탐색의 장단점은?

참고 url​

우투리와 툴툴 - 이분 탐색 알고리즘

이분 탐색 애니메이션

ratsgo 블로그 - 이진탐색 파이썬

기여자​


HelloNaks
📦